//
//  QuJian.cpp
//  cpp
//
//  Created by xueshan1 on 2019/9/5.
//  Copyright © 2019 xueshan1. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <vector>
#include <queue>

using namespace std;
using std :: vector;

//区间
typedef struct Interval_ {
    int start;
    int end;
}Interval;

#pragma mark - 1.给出若干闭合区间，合并所有重叠的部分。

void mergeInterval(vector<Interval>arr){
    //1.需要先排序
    //2.遍历
    vector<Interval> res;
    res.push_back(arr[0]);
    for (int i = 1; i < arr.size(); i++) {
        Interval cur = arr[i];
        Interval resLast = res[res.size() - 1];
        if (cur.start > resLast.end) {//没有重叠,则直接加入
            res.push_back(cur);
        }else  if (cur.start < resLast.end && cur.end > resLast.end) {//交叉
            Interval newOne = {resLast.start, cur.end >resLast.end?cur.end:resLast.end };//end 取大的
            res.push_back(newOne);
        }
        
    }
    
}

#pragma mark - 2.合并两个已排序的区间列表
//合并两个"已排序"的区间列表，并将其作为一个新的有序区间列表返回。新的区间列表应该通过拼接两个列表的区间并按升序排序。
void mergeTwoSortedInterval(vector<Interval>list1, vector<Interval>list2){
    //1.先将两个拼接
    long i = 0;
    long j = 0;
    vector<Interval> mergedList;
    while (i < list1.size() && j < list2.size()) {
        Interval inter1 = list1[i];
        Interval inter2 = list2[j];
        if (inter1.start < inter2.start) {
            mergedList.push_back(inter1);
            i++;
        }else{
            mergedList.push_back(inter2);
            j++;
        }
        
    }
    
    if (i < list1.size() - 1) {
        for (long k = i; k<list1.size(); k++) {
            mergedList.push_back(list1[k]);
        }
    }
    if (j < list2.size() - 1) {
        for (long k = j; k<list2.size(); k++) {
            mergedList.push_back(list2[k]);
        }
    }
    
    //2.再合并当前有序的列表- 一次循环即可
    //题目1
    
}

#pragma mark - 3.数飞机
//给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？
int maxAirPlanes(vector<Interval>times){
    int max = 0;
    
    
    return max;
}
#pragma mark - 4.最小的会议室数量
//给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。
long minMeetRoomCout(vector<Interval>times){
    vector<Interval>rooms;
    rooms.push_back(times[0]);
    for (int i = 1; i<times.size(); i++) {
        Interval newMeet = times[i];
        for (int j = 0; j<rooms.size(); j++) {//已经占用的会议室
            Interval roomMeetTime = rooms[j];
            if (newMeet.start < roomMeetTime.end) {//时间相交了, 需要新增会议室,否则不用新增
                rooms.push_back(newMeet);
                break;
            }
            
        }
        
    }
    
    return rooms.size();
}
